home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / ABUSESRC.ZIP / AbuseSrc / macabuse / imlib / tree.c < prev    next >
C/C++ Source or Header  |  1997-05-20  |  2KB  |  80 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. class btnode
  5. {
  6. protected :
  7.   btnode *Left, *Right;
  8. public :
  9.       btnode *left()                   { return Left; }
  10.       btnode *right()                  { return Right; }
  11.       void    set_right(btnode *right) { Right=right; }
  12.       void    set_left (btnode *left)  { Left=left;   }
  13.   virtual int     compare  (btnode *node) = 0;
  14.   virtual char   *name     ()             = 0;
  15. } ;
  16.  
  17. class btree
  18. {
  19.   void reprint(btnode *n);
  20. protected :
  21.   btnode *root;
  22. public :
  23.            btree() { root=NULL; }
  24.   virtual void insert(btnode *node);
  25.   virtual void remove(btnode *node);
  26.   void         print() { reprint(root); }
  27. } ;
  28.  
  29. void btree::insert(btnode *node)
  30. { btnode *parent,*finder;
  31.   int from_left;
  32.   node->set_right(NULL); node->set_left(NULL);
  33.   if (root)
  34.   { finder=root;
  35.     while (finder)
  36.     { parent=finder;
  37.       if (finder->compare(node)>0)
  38.       { from_left=1; finder=finder->left(); }
  39.       else
  40.       { from_left=0; finder=finder->right(); }
  41.     }
  42.     if (from_left)
  43.       parent->set_left(node);
  44.     else
  45.       parent->set_right(node);
  46.   } else root=node;
  47. }
  48.  
  49. void btree::remove(btnode *node)
  50. {
  51. }
  52.  
  53. void btree::reprint(btnode *n)
  54. {
  55.   if (n)
  56.   { reprint(n->left());
  57.     printf("%s\n",n->name());
  58.     reprint(n->right());
  59.   }
  60. }
  61.  
  62. class btnumber : public btnode
  63. {
  64.   int num;
  65. public :
  66.   btnumber(int x) { num=x; }
  67.   virtual int     compare  (btnode *node)
  68.     { if (num<((btnumber *)node)->num) return -1;
  69.       else return (num> ((btnumber *)node)->num); }
  70.   virtual char   *name     ()
  71.     { static char st[20]; sprintf(st,"%d",num); return st;}
  72. } ;
  73.  
  74. main()
  75. {
  76.   btree bt;
  77.   for (int i=0;i<20;i++)
  78.     bt.insert((btnode *) new btnumber(random(500)));
  79.   bt.print();
  80.